package com.wu.leetcode.leetcode34;

/**
 * Leetcode34-在排序数组中查找元素的第一个和最后一个位置
 * @author lynn
 * @date 2020/11/3 - 10:40
 */
public class Solution {
    public static int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0){
            return new int[]{-1,-1};
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left) >> 1;
            if (nums[mid] == target){
                int l = mid - 1;
                while (l >= 0 && nums[l] == target){
                    l--;
                }
                int r = mid + 1;
                while (r <= right && nums[r] == target){
                    r++;
                }
                return new int[]{++l,--r};
            }else if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return new int[]{-1,-1};
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,7,7,7,8,10};
        int[] ints = searchRange(arr, 7);
        for (int anInt : ints) {
            System.out.print(anInt + " ");
        }
    }
}
